import java.util.Arrays;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution16 {

    public static void main(String args[]) {
        Solution16 s = new Solution16();
        System.out.println(s.threeSumClosest(new int[]{0, 0, 1, -4}, -2));
    }

    public int threeSumClosest(int[] nums, int target) {
        if (nums.length < 3) {
            return 0;
        }
        Arrays.sort(nums);
        int minv = nums[0] + nums[1] + nums[2];
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int a = nums[i];
            int l = 0;
            int r = n - 1;
            while (l < r) {
                if (l == i) {
                    l++;
                    continue;
                }
                if (r == i) {
                    r--;
                    continue;
                }
                minv = cal(minv, a + nums[l] + nums[r], target);
                if (nums[l] + nums[r] + a - target == 0) {
                    return nums[l] + nums[r] + a;
                } else if (nums[l] + nums[r] + a - target < 0) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        return minv;
    }

    public int cal(int a, int b, int target) {
        if (Math.abs(a - target) < Math.abs(b - target)) {
            return a;
        }
        return b;
    }

}
